package pri.zjy.linkedList;

import pri.zjy.linkedList.model.ListNode;

/**
 * @author zhangjy
 * @description 回文链表
 * @date 2025/6/1 23:27
 */
public class IsPalindrome_234 {

    public static void main(String[] args) {

    }

    /**
     * 官解
     * <p>
     * 思路：
     * 1.找到前半部分链表的尾节点。
     *  快慢指针找到第二部分的开始：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
     * 2.反转后半部分链表。
     * 3.判断是否回文。
     * 4.恢复链表。
     * 5.返回结果。
     */
    public boolean isPalindrome2(ListNode head) {
        if (head == null) return true;

        // 快慢指针找到 第二部分的开始：
        ListNode secondStart = getSecondStartByFastAndSlow(head);
        // 反转后的第二部分开始
        ListNode reverseSecondStart = reverseList(secondStart);
        // 快慢指针找到 第一部分的尾部：
//        ListNode firstEnd = getFirstEndByFastAndSlow(head);
//        ListNode secondStart = reverseList(firstEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = reverseSecondStart;
        while (p1 != null && p2 != null) {
            // 不同直接返回
            if (p1.val != p2.val) return false;

            // 相同，则判断下一个节点
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    private ListNode getSecondStartByFastAndSlow(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode getFirstEndByFastAndSlow(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 个解
     * <p>
     * 思路：将链表分为两半，然后将其中一部分反转，最后遍历比较反转后的链表和另一部分链表
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;

        // 1.统计链表长度
        int length = 0;
        ListNode dummyHead = head;
        while (dummyHead != null) {
            length++;
            dummyHead = dummyHead.next;
        }

        // 单个节点一定是回文链表
        if (length == 1) return true;

        // 2.反转前半部分链表
        ListNode cur = head;
        ListNode pre = new ListNode(-1, cur);
        int curLength = 0;
        while (curLength < length / 2) {
            curLength++;
            ListNode tmp = cur.next;
            // 反转
            cur.next = pre;
            // 后移
            pre = cur;
            cur = tmp;
        }

        // 奇数长度，cur多后移一位
        if (length % 2 != 0) cur = cur.next;

        // 3.遍历前后两部分链表，若出现不同，表示不是回文链表
        while (pre != null && cur != null) {
            // 不同
            if (pre.val != cur.val) return false;
            // 相同，则判断下一个节点
            pre = pre.next;
            cur = cur.next;
        }
        return true;
    }

}
